package q41_firstMissingPositive;

import java.util.Arrays;

public class Solution_1 {
    public static void main(String[] args) {
        int[] arr = {1,2,0};
        System.out.println(firstMissingPositive(arr));
    }

    public static int firstMissingPositive(int[] nums) {
        // 排序
        Arrays.sort(nums);
        // 先考虑只有一位数的情况
        if (nums.length == 1) {
            if (nums[0] != 1) {
                return 1;
            }else {
                return 2;
            }
        }

        // 不止一位数的情况
        if (nums[nums.length - 1] <= 0) {
            return 1;
        }

        if(nums[0] == 0) {
            return PositionSearch(nums,1,nums.length - 1);
        }else if (nums[0] > 0){
            // 如果第一位数字也大于0，那么就直接利用算法查找缺失的正数
            return PositionSearch(nums, 0, nums.length - 1);
        }else {
            // 双指针法找出第一个大于0的数的位置
            return PositionSearch(nums,absSearch(nums),nums.length - 1);
        }

    }

    public static int PositionSearch(int[] arr,int start,int end){
        if (arr[start] != 1) {
            return 1;
        }
        int bin = end;
        while((end - start) > 1) {
            if(arr[end] > (end - start + arr[start])){
                bin = end;
                end = start + (end - start)/2 + 1;
            }else{
                start = end;
                end = bin;
            }
        }

        return (arr[end] - arr[start] == 1) ? arr[end] + 1 : arr[start] + 1;


    }

    public static int absSearch(int[] ary) {
        // 双指针
        int p1 = 0;
        int p2 = ary.length - 1;
        // 实际上是要找出绝对值最小的数的索引位置
        while(p2 - p1 > 1){
            if (Math.abs(ary[p1]) <= Math.abs(ary[p2])) {
                p2 = (p1 + p2)/2;
            }else if(Math.abs(ary[p1]) > Math.abs(ary[p2])){
                p1 = (p1 + p2)/2;
            }
        }

        return ary[p1] > 0 ? p1 : p2;

    }
}
